/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include<iostream>
using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
	treeHeight=0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{	
	RC rc=pf.open(indexname, mode);
	if(rc!=0)
		return rc;
	//cout<<"inside indexopn point 1"<<endl;
	char buffer[PageFile::PAGE_SIZE];
	pf.read(INDEX_PID,buffer);

   // cout<<"inside indexopn point 2"<<endl;
    char* ptr= buffer;
	//cout<<"inside open"<<endl;
	rootPid=*(PageId *) ptr;
	ptr=ptr+sizeof(PageId);
	//cout<<"inside open index"<<endl;
	//cout<<"treeHeight is  "<<endl;
	treeHeight= (*(int *) ptr);
	//cout<<treeHeight;
	ptr=ptr+sizeof(int);
	smallestKey=(*(int *)ptr);

//	cout<<"retrieving info "<<"treeheight is " <<treeHeight <<"rootPid "<<rootPid<<"smallest key "<<smallestKey;


	return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */

RC BTreeIndex::clear()
{ treeHeight=0;
  rootPid=-1;

}


RC BTreeIndex::close()
{	char buffer[PageFile::PAGE_SIZE];      // buffer: rootPid ,  treeHeiht, smallestKey
	char* ptr= buffer;
	(*(PageId *)ptr) = rootPid;
	ptr=ptr+sizeof(PageId);
	(*(int *)ptr)=treeHeight;
	ptr=ptr+sizeof(int);
	(*(int *)ptr)=smallestKey;
	RC rc;
	if(rc=pf.write(INDEX_PID,buffer)!=0)
		return rc;
    return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insertEmptyCase(int key, const RecordId& rid)
{	
	//cout<<"we get heere1 in insertemptyCase"<<endl;
	RC rc;
	BTLeafNode ln;
	ln.insert(key, rid);
	PageId leafPid=pf.endPid();
	if(leafPid==0) leafPid++; //very important!! pid 0 is reserved for treeindex 
	if(rc=ln.write(leafPid,pf)!=0) return rc;
	treeHeight++;
	smallestKey=key;
	rootPid=leafPid;
	//cout<<"inside insertEmptycase , after insertion rootPid is "<<rootPid<<endl;

	return 0;
	


}


RC BTreeIndex::insert(int key, const RecordId& rid)
{	
	//cout<<"trying to insert key :" <<key<<endl;
	//cout<<"tree height is ";
	//cout<<treeHeight;
	if(treeHeight==0)
		return insertEmptyCase(key,rid);
	if (key<smallestKey)
		smallestKey=key;
	//clear the stack
	while(!traversePath.empty()){
		traversePath.pop();
	}
	IndexCursor cursor;
	locate( key ,  cursor);
	PageId leafPid=cursor.pid;
	//cout<<"inside insert , after locate ,leafPid is "<<leafPid<<"for key "<<key<<endl;
	BTLeafNode ln;
	RC rc=ln.read (leafPid,pf);
	if (rc!=0) return rc;
    rc=ln.insert(key , rid);
	if (rc==0) {
		//cout<<"insertion is successful "<<endl;
		rc=ln.write(leafPid,pf);
		if(rc!=0){
			//cout<<"write is not successful"<<endl;
			return rc;
		}
		return 0;
	}
	else if(rc==RC_NODE_FULL) {
		BTLeafNode sibling; // create a sibiling leaf node
		int siblingKey; // store the first key in sibling node
		PageId sibPid;
		sibPid=pf.endPid();
		ln.insertAndSplit(key,rid,sibling,siblingKey); 
		ln.setNextNodePtr(sibPid);
		ln.write(leafPid,pf);
		sibling.write(sibPid,pf);
		if (treeHeight==1) {// this node is a leaf root 
			BTNonLeafNode newRoot;
			newRoot.initializeRoot(leafPid,  siblingKey,  sibPid);
			rootPid=pf.endPid();
			newRoot.write(rootPid,pf);
			treeHeight++;
			return 0;
		}
		PageId parentPid=traversePath.top();
		traversePath.pop();
		return insertToNonleaf(parentPid, siblingKey,sibPid,traversePath);
	}
	else return rc;
		

}


RC BTreeIndex::insertToNonleaf(PageId toReadPid, int key, PageId toInsertPid ,stack<PageId>& traversePath)
{	RC rc;
	BTNonLeafNode nln;
	if(rc=nln.read(toReadPid, pf)!=0) return rc;
	rc=nln.insert(key , toInsertPid);
	if (rc==0){
		nln.write(toReadPid,pf);
		return 0;
	}
	else if(rc==RC_NODE_FULL) {
		BTNonLeafNode sibling; // create a sibiling non leaf node
		int midKey; // store the mid key 
		PageId sibPid;
		sibPid=pf.endPid();
		nln.insertAndSplit(key,toInsertPid,sibling,midKey); 
		nln.write(toReadPid,pf);
		sibling.write(sibPid,pf);
		if (traversePath.empty()) {// this node is the root 
			BTNonLeafNode newRoot;
			newRoot.initializeRoot(toReadPid,  key,  sibPid);
			rootPid=pf.endPid();
			newRoot.write(rootPid,pf);
			treeHeight++;
			return 0;
		}
		PageId parentPid=traversePath.top();
		traversePath.pop();
		return insertToNonleaf(parentPid, midKey,sibPid,traversePath);
	}
	
	else return rc;



}
/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{	// remains to check the empty tree cases
	if(rootPid==-1) // tree is empty 
		return  RC_NO_SUCH_RECORD;
	RC rc;
	int level=1;  // root node has level 1
	BTNonLeafNode nln;
	PageId pid=rootPid;
	
	// root already exists 
	// level is the level of node we are about to read
	while(level < treeHeight){
//		cout<<"oue iteration  "<<endl;
		if(rc=nln.read(pid,pf)!=0)
			return rc;
			traversePath.push(pid);   //we push the current node pid onto the stack. after the traversal ,the stack contains pid of nonleafnodes
//			cout<<"we just pushed pid "<<pid<<endl;
//			cout<<"trying to locate searchkey "<<searchKey<<endl;
			nln.locateChildPtr(searchKey, pid);
//			cout<<"after loacate Child ptr, we decide to insert into pid "<<pid<<endl;
			level++;
	}
	// at this point ,  pid is the page id of the leaf node

	BTLeafNode ln;
	if (rc=ln.read(pid,pf)!=0)
		return rc;
	int eid;
	rc=ln.locate(searchKey,eid);
	// even if we didnt find such a entry, we set cursor.pid to be the pid of node so that insert method can use this information
	cursor.pid=pid;
	if (rc!=0)
		return rc;	
	cursor.eid=eid;

    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{	BTLeafNode ln;
	PageId pidToRead=cursor.pid;
	int eidToRead=cursor.eid;
	RC rc;
	if(rc=ln.read(pidToRead,pf)!=0)
		return rc;
	rc=ln.readEntry(eidToRead, key, rid);
	if(rc!=0)
		return rc;
	if (eidToRead == ln.getKeyCount()-1){ // we just read the last entry of the node
		cursor.eid=0;
		cursor.pid=ln.getNextNodePtr(); //yet to check get Next Node Ptr
	}
	else if (eidToRead<ln.getKeyCount()-1){
		cursor.eid++;
	}
    return 0;
}
